#include <stdio.h>
#include <stdlib.h>

typedef struct BNode{
    BNode * lchild;
    BNode * rchild;
    int data;
}BNode,*BTree;

/***
 *          1
 *      2       3
 *   4              5
 * */
bool GetLastCommonParent(BTree T, BNode *n1, BNode *n2) {
    if (!T)
        return false;
    
    if (T == n1 || T == n2)
        return true;
    
    bool left = GetLastCommonParent(T->lchild,n1,n2);
    bool right = GetLastCommonParent(T->rchild,n1,n2);
    if (left && right)
    {
        printf("%d",T->data);
        return false;
    }

    return left || right;
}

// 测试
void print(BTree T) {
    if (T) {
        printf("%d ",T->data);
        print(T->lchild);
        print(T->rchild);
    }
}

BNode * GetNode(int x) {
    BNode *node = (BNode *)malloc(sizeof(BNode));
    node->data = x;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

int main() {
    BTree T = GetNode(1);
    T->lchild = GetNode(2);
    T->rchild = GetNode(3);
    T->lchild->lchild = GetNode(4);
    T->rchild->rchild = GetNode(5);
    T->rchild->lchild = GetNode(6);
    GetLastCommonParent(T, T->rchild->lchild, T->rchild->rchild);
    return 0;
}